#include <iostream>
#include <vector>

using namespace std;

template <class T>
struct HashNode
{
	T _data;
	HashNode* _next;
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

template <class K>
struct _hash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct _hash<string>
{
	size_t operator()(const string& key)
	{
		size_t hashi = 0;
		for (auto e : key)
		{
			hashi += e;
			hashi *= 131;
		}
		return hashi;
	}
};

template <class K, class T, class KOfT, class hash = _hash<K>>
class HashTable;

template <class K, class T, class KOfT,class hash = _hash<K>>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, KOfT, hash> Self;
	typedef HashTable<K, T, KOfT, hash> Table;

	Node* _node;
	Table* _ptable;

	HashIterator(Node* node, Table* table)
		:_node(node)
		, _ptable(table)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KOfT kot;
			hash h;
			size_t hashi = h(kot(_node->_data));

			++hashi;
			while (hashi < _ptable->_table.size())	
			{
				if (_ptable[hashi])
				{
					_node = _ptable[hashi];
					break;
				}
				++hashi;
			}

			if (hashi == _ptable->_table.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

	bool operator!=(const Self& it)
	{
		return it._node != this->_node;
	}
};

template <class K, class T, class KOfT, class hash = _hash<K>>
class HashTable
{
public:
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KOfT, hash> Self;
	typedef HashIterator<K, T, KOfT, hash> iterator;

	HashTable(size_t size = 10)
	{
		_table.resize(size, nullptr);
		_n = 0;
	}

	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}

	iterator begin()
	{
		hash hs;
		KOfT kot;

		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				return iterator(_table[i], this);
			}
		}

		return iterator(nullptr, this);
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	Node* Find(const K& key)
	{
		hash hs;
		size_t hashi = hs(key) % _table.size();
		Node* ptr = _table[hashi];
		while (ptr)
		{
			KOfT kot;
			if (kot(ptr->_data) == key)
				return ptr;
			ptr = ptr->_next;
		}
		return nullptr;
	}

	bool Insert(const T& data)
	{
		hash hs;
		KOfT kot;

		if (Find(kot(data)))
			return false;

		if (_n == _table.size())
		{
			size_t newsize = _n * 2;
			vector<Node*> newtable(newsize, nullptr);

			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = hs(kot(data)) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
			_table.swap(newtable);
		}

		size_t hashi = hs(kot(data)) % _table.size();
		Node* newdata = new Node(data);

		newdata->_next = _table[hashi];
		_table[hashi] = newdata;

		++_n;
		return true;
	}

	bool Erase(const K& key)
	{
		Node* ptr = Find(key);
		hash hs;
		KOfT kot;

		if (ptr)
		{
			size_t hashi = hs(key) % _table.size();
			Node* cur = _table[hashi];

			if (cur->_next == nullptr)
			{
				_table[hashi] = nullptr;
				--_n;
				return true;
			}

			Node* pre = nullptr;
			while (cur)
			{
				Node* next = cur->_next;

				if (kot(cur->_data) == key)
				{
					pre->_next = cur->_next;
					delete cur;
					--_n;
					return true;
				}

				pre = cur;
				cur = next;
			}
		}
		return false;
	}

private:
	vector<Node*> _table;
	size_t _n;
};